package lru

import (
	"sync"
)

const (
	BUCKET = 100
)

var pool = sync.Pool{New: func() interface{} {
	return lruNode{}
}}

type lruNode struct {
	prev *lruNode //按照时间大小连接，双链表
	next *lruNode //按照时间大小连接，双链表

	key   string      // lru key
	value interface{} // lru value

	hNext *lruNode // 解决hash冲突的，单链表
}

func (that lruNode) Reset() {
	that.key = ""
	that.value = nil
	that.hNext = nil
	that.prev = nil
	that.next = nil
}

type LRUCache struct {
	nodes []lruNode // 充当map角色，下标代表key
	// 所有节点按照访问先后时间都被串联在next组成的链中
	head *lruNode // lru head node 很久没被访问的节点，即将被淘汰的节点
	tail *lruNode // lru tail node 最新被访问的节点

	capacity int // cache cap
	used     int //

	m sync.Mutex // mutex
}

func NewLRUCache(capacity int) LRUCache {
	return LRUCache{
		nodes:    make([]lruNode, BUCKET), //hash表的槽位只有100个
		head:     nil,
		tail:     nil,
		capacity: capacity,
		used:     0,
	}
}

func (that *LRUCache) Get(key string) interface{} {
	that.m.Lock()
	defer that.m.Unlock()
	if that.tail == nil {
		return nil
	}

	if tmp := that.searchNode(key); tmp != nil {
		that.moveToTail(tmp)
		return tmp.value
	}
	return nil
}

func (that *LRUCache) Put(key string, value interface{}) {
	// 1. 首次插入数据
	// 2. 插入数据不在 LRU 中
	// 3. 插入数据在 LRU 中
	// 4. 插入数据不在 LRU 中, 并且 LRU 已满

	that.m.Lock()
	defer that.m.Unlock()

	if tmp := that.searchNode(key); tmp != nil {
		tmp.value = value
		that.moveToTail(tmp)
		return
	}
	that.addNode(key, value)

	if that.used > that.capacity {
		that.delNode()
	}
}

func (that *LRUCache) addNode(key string, value interface{}) {
	newNode := pool.Get().(lruNode)
	newNode.key = key
	newNode.value = value
	defer func() {
		newNode.Reset()
		pool.Put(newNode)
	}()

	tmp := &that.nodes[hash(key)]
	// 将newNode节点插入tmp和tmp.hNext之间
	newNode.hNext = tmp.hNext
	tmp.hNext = &newNode

	that.used++
	// tail没有指向任何节点
	if that.tail == nil {
		that.tail, that.head = &newNode, &newNode
		return
	}
	that.tail.next = &newNode
	newNode.prev = that.tail
	that.tail = &newNode
}

func (that *LRUCache) delNode() {
	if that.head == nil {
		return
	}
	// 找到head节点所在hash桶的第一个节点
	hPrev := &that.nodes[hash(that.head.key)] //hPrev表示该hash桶下的第一个节点
	tmp := hPrev.hNext                        // 取出hash桶里的下一个节点

	for tmp != nil && tmp.key != that.head.key {
		hPrev = tmp
		tmp = tmp.hNext
	}
	// head就是hash桶的第一个节点
	if tmp == nil {
		return
	}
	// 找到了head所在位置，此时tmp就是head，hPrev是head的上一个节点
	// 在hash桶中删除head
	hPrev.hNext = tmp.hNext

	// 在时间链条上删除head，并重新指定head
	that.head = that.head.next
	that.head.prev = nil
	that.used--
}

func (that *LRUCache) searchNode(key string) *lruNode {
	if that.tail == nil {
		return nil
	}

	// 查找
	tmp := that.nodes[hash(key)].hNext
	for tmp != nil {
		if tmp.key == key {
			return tmp
		}
		tmp = tmp.hNext
	}
	return nil
}

func (that *LRUCache) moveToTail(node *lruNode) {
	if that.tail == node {
		return
	}
	// 如果这个节点是head，也就是即将被淘汰的节点
	if node == that.head {
		// 更新比node节点新一点的节点为head节点
		that.head = node.next
		that.head.prev = nil
	} else {
		node.next.prev = node.prev // 连接prev
		node.prev.next = node.next //连接next
	}

	node.next = nil       // node节点变成了最新节点，所以next指向nil
	that.tail.next = node // 将node节点添加到tail的前面
	node.prev = that.tail // 将node的前驱连接到tail

	that.tail = node
}

func hash(key string) int {
	bytesKey := []byte(key)
	byteInt := uint8(0)
	for _, v := range bytesKey {
		byteInt += v
	}
	hashKey := int(byteInt) % BUCKET
	return hashKey
}
